package history

import "container/list"

/**
 * @Description: 飞榴科技一面
 * @Keyword: 快速排序
 * @Author: kami
 * @Date: 2022/6/6 16:29
 **/
func quickSort20220606(nums []int) {
	quickSort0606(nums, 0, len(nums)-1)
}
func quickSort0606(nums []int, low, high int) {
	if low < high {
		var left = low
		var right = high
		var pviot = nums[low]
		for left < right {
			for left < right && nums[right] > pviot {
				right--
			}
			if left < right {
				nums[left] = nums[right]
				left++
			}
			for left < right && nums[left] < pviot {
				left++
			}
			if left < right {
				nums[right] = nums[left]
				right--
			}
		}
		nums[left] = pviot
		quickSort0606(nums, low, left-1)
		quickSort0606(nums, left+1, high)
	}
}

/**
 * @Description: 实现有序map
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/6 16:35
 **/
type OrderedMap struct {
	//存储 k-v,使用 *list.Element 当做 value 是利用 map O(1) 的性能找到 list 中的 element
	kv map[interface{}]*list.Element
	//按顺序存储 k-v，保证插入、删除的时间复杂度O(1)
	ll *list.List
}
